If you plan to travel around the countryside without a guide, take a GPS and get some maps. The "Mongolia Road Atlas" is available in many bookstores, it is over 60 pages and covers the whole country: note there is a latin character version and cyrillic character version, in the countryside most people won't understand the latin version. More detailed maps are available at the Mongolian Government Map Store. These maps are 1:500,000. Also some other special purpose maps and a very good map of downtown Ulaanbaatar. The map store is on Ih Toiruu St. Go west from the State Department store on the main street, called Peace, Peace and Friendship, or Ekhtavan Ave, two blocks to the large intersection with traffic lights, Turn right North and the map store is about half way along the block. There is an Elba electronic appliance store set back from the street, a yellow and blue building, the next building is a large Russian style office building 4 floors in height, the map store entrance is on the west side, toward the south end of the building, it lines up with the North wall of the Elba building.
Whichever method of long-distance travel is chosen, keep in mind that everything in Mongolia has a tendency to break down. Don't be shocked if part of the suspension breaks and the driver jimmy-rigs a carved wooden block in the place of a mount. For more serious breakdowns, it can easily take an entire day or longer for somebody to come along and help, so leave plenty of slack in itineraries. Finally, Mongolians are rather notorious for being late. A bus that is scheduled to leave at 8AM will probably not be out of the city till almost 11AM.
By Horse
For local travel, horse-back is a good option. Note, however, that Mongolians ride on wooden saddles, so if you value your buttocks it's probably a good idea to pick up a leather, Russian saddle in UB.
By Minivan
Public countryside taxis and minivans offer more destinations than coaches and many more than train, especially between provinces. They are more dangerous than coaches and trains. Most drivers don't respect the traffic rules. Countryside taxis and minivans leave when full. They always say they will go "now" "odo" but it's rarely true and you can wait hours before they really go. See how many people are already sitting inside the vehicle to have an idea of how long you'll wait.
On foot
Another great alternative is to simply walk. Since camping is possible anywhere, resting is never a problem. Wherever there is water there are nomads, and if you stick to the major dirt-roads you will encounter plenty of guanz, who can provide huge cheap meals to keep you going. Adopting the Mongolian style of sleeping outdoors is also an option - wrap yourself in wool blankets and then cover yourself with a Russian raincoat essentially a tarp in the form of a trench coat, and simply plop yourself down on the ground. One night sleeping this way gives a whole new appreciation for the wonders of sleeping bags and bivvy sacks/tents.
By train
There is only one railway company in Mongolia, owned by the Russian and Mongolian States: "Mongolian railway". It is probably the best way to experience something of the communist time, even if it has evolved a bit since then. Ulaanbaatar railway agents consider more often the passenger as a potential rule breaker than as a client. The railway network is poor, consisting mainly in the Irkutsk-Beijing trans-mongolian way with a few extensions. Trains are extremely slow. They usually leave on time, and arrive on time or less than 20 min late.
The local trains stop at many small stations in the countryside. For example, there is the small town of Batsumber, located about 34km north of Ulaanbaatar as the crow flies longer on the train. Take your camping gear and hike to the mountains about 10km east of the town. There are two streams flowing west out of the mountains, hike and camp along the streams. There is a small restaurant, and food shops in the town.
By Chartered Jeep
It is also possible to charter a Jeep and driver for private use. Prices are typically negotiated by the kilometer. While far more expensive than sharing a ride with the locals, this means of transport is considerably more convenient and allows you to visit more remote sites. It can also be quite convenient to hire a guide to use during the length of your stay. Doing so can allow you to travel without worrying about taxi drivers wanting to overcharge up to 10X just for being a foreigner.